home *** CD-ROM | disk | FTP | other *** search
/ Aminet 1 (Walnut Creek) / Aminet - June 1993 [Walnut Creek].iso / aminet / util / edit / jed207.lha / src / regexp.lha / regexp.c < prev    next >
C/C++ Source or Header  |  1993-01-14  |  30KB  |  1,247 lines
  1. /*
  2.  * regcomp and regexec -- regsub and regerror are elsewhere @(#)regexp.c 1.3
  3.  * of 18 April 87
  4.  *
  5.  * Copyright (c) 1986 by University of Toronto. Written by Henry Spencer.  Not
  6.  * derived from licensed software.
  7.  *
  8.  * Permission is granted to anyone to use this software for any purpose on any
  9.  * computer system, and to redistribute it freely, subject to the following
  10.  * restrictions:
  11.  *
  12.  * 1. The author is not responsible for the consequences of use of this
  13.  * software, no matter how awful, even if they arise from defects in it.
  14.  *
  15.  * 2. The origin of this software must not be misrepresented, either by explicit
  16.  * claim or by omission.
  17.  *
  18.  * 3. Altered versions must be plainly marked as such, and must not be
  19.  * misrepresented as being the original software.
  20.  *
  21.  * Beware that some of this code is subtly aware of the way operator precedence
  22.  * is structured in regular expressions.  Serious changes in
  23.  * regular-expression syntax might require a total rethink.
  24.  */
  25.  
  26. /*
  27.  * CHANGED, 14-Jan-93, by J.Harper,
  28.  * added #ifdef __STDC__ prototype sections so I can use registerized
  29.  * arguments
  30.  */
  31.  
  32. #include <stdio.h>
  33. #ifdef AMIGA
  34. #undef min
  35. #include "regexp.h"
  36. #else
  37. #include <regexp.h>
  38. #endif
  39. #include "regmagic.h"
  40.  
  41. #ifdef __STDC__
  42. #include <string.h>
  43. #include <stdlib.h>
  44. #endif
  45.  
  46. /*
  47.  * The "internal use only" fields in regexp.h are present to pass info from
  48.  * compile to execute that permits the execute phase to run lots faster on
  49.  * simple cases.  They are:
  50.  *
  51.  * regstart    char that must begin a match; '\0' if none obvious reganch
  52.  * is the match anchored (at beginning-of-line only)? regmust    string
  53.  * (pointer into program) that match must include, or NULL regmlen
  54.  * length of regmust string
  55.  *
  56.  * Regstart and reganch permit very fast decisions on suitable starting points
  57.  * for a match, cutting down the work a lot.  Regmust permits fast rejection
  58.  * of lines that cannot possibly match.     The regmust tests are costly enough
  59.  * that regcomp() supplies a regmust only if the r.e. contains something
  60.  * potentially expensive (at present, the only such thing detected is * or +
  61.  * at the start of the r.e., which can involve a lot of backup).  Regmlen is
  62.  * supplied because the test in regexec() needs it and regcomp() is computing
  63.  * it anyway.
  64.  */
  65.  
  66. /*
  67.  * Structure for regexp "program".  This is essentially a linear encoding of
  68.  * a nondeterministic finite-state machine (aka syntax charts or "railroad
  69.  * normal form" in parsing technology).  Each node is an opcode plus a "next"
  70.  * pointer, possibly plus an operand.  "Next" pointers of all nodes except
  71.  * BRANCH implement concatenation; a "next" pointer with a BRANCH on both
  72.  * ends of it is connecting two alternatives.    (Here we have one of the
  73.  * subtle syntax dependencies:    an individual BRANCH (as opposed to a
  74.  * collection of them) is never concatenated with anything because of
  75.  * operator precedence.)  The operand of some types of node is a literal
  76.  * string; for others, it is a node leading into a sub-FSM.  In particular,
  77.  * the operand of a BRANCH node is the first node of the branch. (NB this is
  78.  * *not* a tree structure:  the tail of the branch connects to the thing
  79.  * following the set of BRANCHes.)  The opcodes are:
  80.  */
  81.  
  82. /* definition    number    opnd?    meaning */
  83. #define END    0        /* no    End of program. */
  84. #define BOL    1        /* no    Match "" at beginning of line. */
  85. #define EOL    2        /* no    Match "" at end of line. */
  86. #define ANY    3        /* no    Match any one character. */
  87. #define ANYOF    4        /* str    Match any character in this string. */
  88. #define ANYBUT    5        /* str    Match any character not in this
  89.                  * string. */
  90. #define BRANCH    6        /* node Match this alternative, or the
  91.                  * next... */
  92. #define BACK    7        /* no    Match "", "next" ptr points backward. */
  93. #define EXACTLY 8        /* str    Match this string. */
  94. #define NOTHING 9        /* no    Match empty string. */
  95. #define STAR    10        /* node Match this (simple) thing 0 or more
  96.                  * times. */
  97. #define PLUS    11        /* node Match this (simple) thing 1 or more
  98.                  * times. */
  99. #define OPEN    20        /* no    Mark this point in input as start of
  100.                  * #n. */
  101. /* OPEN+1 is number 1, etc. */
  102. #define CLOSE    30        /* no    Analogous to OPEN. */
  103.  
  104. /*
  105.  * Opcode notes:
  106.  *
  107.  * BRANCH    The set of branches constituting a single choice are hooked together
  108.  * with their "next" pointers, since precedence prevents anything being
  109.  * concatenated to any individual branch.  The "next" pointer of the last
  110.  * BRANCH in a choice points to the thing following the whole choice.  This
  111.  * is also where the final "next" pointer of each individual branch points;
  112.  * each branch starts with the operand node of a BRANCH node.
  113.  *
  114.  * BACK        Normal "next" pointers all implicitly point forward; BACK exists to
  115.  * make loop structures possible.
  116.  *
  117.  * STAR,PLUS    '?', and complex '*' and '+', are implemented as circular
  118.  * BRANCH structures using BACK.  Simple cases (one character per match) are
  119.  * implemented with STAR and PLUS for speed and to minimize recursive
  120.  * plunges.
  121.  *
  122.  * OPEN,CLOSE    ...are numbered at compile time.
  123.  */
  124.  
  125. /*
  126.  * A node is one char of opcode followed by two chars of "next" pointer.
  127.  * "Next" pointers are stored as two 8-bit pieces, high order first.  The
  128.  * value is a positive offset from the opcode of the node containing it. An
  129.  * operand, if any, simply follows the node.  (Note that much of the code
  130.  * generation knows about this implicit relationship.)
  131.  *
  132.  * Using two bytes for the "next" pointer is vast overkill for most things, but
  133.  * allows patterns to get big without disasters.
  134.  */
  135. #define OP(p)    (*(p))
  136. #define NEXT(p) (((*((p)+1)&0377)<<8) + (*((p)+2)&0377))
  137. #define OPERAND(p)    ((p) + 3)
  138.  
  139. /*
  140.  * See regmagic.h for one further detail of program structure.
  141.  */
  142.  
  143.  
  144. /*
  145.  * Utility definitions.
  146.  */
  147. #ifndef CHARBITS
  148. #define UCHARAT(p)    ((int)*(unsigned char *)(p))
  149. #else
  150. #define UCHARAT(p)    ((int)*(p)&CHARBITS)
  151. #endif
  152.  
  153. #define FAIL(m) { regerror(m); return(NULL); }
  154. #define ISMULT(c)    ((c) == '*' || (c) == '+' || (c) == '?')
  155. #define META    "^$.[()|?+*\\"
  156.  
  157. /*
  158.  * Flags to be passed up and down.
  159.  */
  160. #define HASWIDTH    01    /* Known never to match null string. */
  161. #define SIMPLE        02    /* Simple enough to be STAR/PLUS operand. */
  162. #define SPSTART        04    /* Starts with * or +. */
  163. #define WORST        0    /* Worst case. */
  164.  
  165. /*
  166.  * Global work variables for regcomp().
  167.  */
  168. static char    *regparse;    /* Input-scan pointer. */
  169. static int    regnpar;    /* () count. */
  170. static char    regdummy;
  171. static char    *regcode;    /* Code-emit pointer; ®dummy = don't. */
  172. static long    regsize;    /* Code size. */
  173.  
  174. /*
  175.  * Forward declarations for regcomp()'s friends. 
  176.  */
  177. #ifndef STATIC
  178. #define STATIC    static
  179. #endif
  180. #ifdef __STDC__
  181. STATIC char    *reg(int, int *);
  182. STATIC char    *regbranch(int *);
  183. STATIC char    *regpiece(int *);
  184. STATIC char    *regatom(int *);
  185. STATIC char    *regnode(char);
  186. STATIC char    *regnext(char *);
  187. STATIC void    regc(char);
  188. STATIC void    reginsert(char, char *);
  189. STATIC void    regtail(char *, char *);
  190. STATIC void    regoptail(char *, char *);
  191. extern void    regerror(char *);
  192. #ifdef STRCSPN
  193. int        strcspn(char *, char *);
  194. #endif /* STRCSPN */
  195. #else
  196. STATIC char    *reg();
  197. STATIC char    *regbranch();
  198. STATIC char    *regpiece();
  199. STATIC char    *regatom();
  200. STATIC char    *regnode();
  201. STATIC char    *regnext();
  202. STATIC void    regc();
  203. STATIC void    reginsert();
  204. STATIC void    regtail();
  205. STATIC void    regoptail();
  206. #ifdef STRCSPN
  207. int        strcspn();
  208. #endif /* STRCSPN */
  209. #endif /* __STDC__ */
  210. /*
  211.  * - regcomp - compile a regular expression into internal code
  212.  *
  213.  * We can't allocate space until we know how big the compiled form will be, but
  214.  * we can't compile it (and thus know how big it is) until we've got a place
  215.  * to put the code.  So we cheat:  we compile it twice, once with code
  216.  * generation turned off and size counting turned on, and once "for real".
  217.  * This also means that we don't allocate space until we are sure that the
  218.  * thing really will compile successfully, and we never have to move the code
  219.  * and thus invalidate pointers into it.  (Note that it has to be in one
  220.  * piece because free() must be able to free it all.)
  221.  *
  222.  * Beware that the optimization-preparation code in here knows about some of the
  223.  * structure of the compiled regexp.
  224.  */
  225. regexp           *
  226. regcomp(exp)
  227.     char       *exp;
  228. {
  229.     register regexp *r;
  230.     register char  *scan;
  231.     register char  *longest;
  232.     register int    len;
  233.     int            flags;
  234.  
  235.     if (exp == NULL)
  236.     FAIL("NULL argument");
  237.  
  238.     /* First pass: determine size, legality. */
  239.     regparse = exp;
  240.     regnpar = 1;
  241.     regsize = 0L;
  242.     regcode = ®dummy;
  243.     regc(MAGIC);
  244.     if (reg(0, &flags) == NULL)
  245.     return (NULL);
  246.  
  247.     /* Small enough for pointer-storage convention? */
  248.     if (regsize >= 32767L)    /* Probably could be 65535L. */
  249.     FAIL("regexp too big");
  250.  
  251.     /* Allocate space. */
  252.     r = (regexp *) malloc(sizeof(regexp) + (unsigned) regsize);
  253.     if (r == NULL)
  254.     FAIL("out of space");
  255.  
  256.     /* Second pass: emit code. */
  257.     regparse = exp;
  258.     regnpar = 1;
  259.     regcode = r->program;
  260.     regc(MAGIC);
  261.     if (reg(0, &flags) == NULL)
  262.     return (NULL);
  263.  
  264.     /* Dig out information for optimizations. */
  265.     r->regstart = '\0';         /* Worst-case defaults. */
  266.     r->reganch = 0;
  267.     r->regmust = NULL;
  268.     r->regmlen = 0;
  269.     scan = r->program + 1;    /* First BRANCH. */
  270.     if (OP(regnext(scan)) == END) {    /* Only one top-level choice. */
  271.     scan = OPERAND(scan);
  272.  
  273.     /* Starting-point info. */
  274.     if (OP(scan) == EXACTLY)
  275.         r->regstart = *OPERAND(scan);
  276.     else if (OP(scan) == BOL)
  277.         r->reganch++;
  278.  
  279.     /*
  280.      * If there's something expensive in the r.e., find the longest
  281.      * literal string that must appear and make it the regmust.  Resolve
  282.      * ties in favor of later strings, since the regstart check works
  283.      * with the beginning of the r.e. and avoiding duplication
  284.      * strengthens checking.  Not a strong reason, but sufficient in the
  285.      * absence of others.
  286.      */
  287.     if (flags & SPSTART) {
  288.         longest = NULL;
  289.         len = 0;
  290.         for (; scan != NULL; scan = regnext(scan))
  291.         if (OP(scan) == EXACTLY && strlen(OPERAND(scan)) >= len) {
  292.             longest = OPERAND(scan);
  293.             len = strlen(OPERAND(scan));
  294.         }
  295.         r->regmust = longest;
  296.         r->regmlen = len;
  297.     }
  298.     }
  299.     return (r);
  300. }
  301.  
  302. /*
  303.  * - reg - regular expression, i.e. main body or parenthesized thing
  304.  *
  305.  * Caller must absorb opening parenthesis.
  306.  *
  307.  * Combining parenthesis handling with the base level of regular expression is a
  308.  * trifle forced, but the need to tie the tails of the branches to what
  309.  * follows makes it hard to avoid.
  310.  */
  311. static char    *
  312. reg(paren, flagp)
  313.     int            paren;    /* Parenthesized? */
  314.     int           *flagp;
  315. {
  316.     register char  *ret;
  317.     register char  *br;
  318.     register char  *ender;
  319.     register int    parno;
  320.     int            flags;
  321.  
  322.     *flagp = HASWIDTH;        /* Tentatively. */
  323.  
  324.     /* Make an OPEN node, if parenthesized. */
  325.     if (paren) {
  326.     if (regnpar >= NSUBEXP)
  327.         FAIL("too many ()");
  328.     parno = regnpar;
  329.     regnpar++;
  330.     ret = regnode(OPEN + parno);
  331.     } else
  332.     ret = NULL;
  333.  
  334.     /* Pick up the branches, linking them together. */
  335.     br = regbranch(&flags);
  336.     if (br == NULL)
  337.     return (NULL);
  338.     if (ret != NULL)
  339.     regtail(ret, br);    /* OPEN -> first. */
  340.     else
  341.     ret = br;
  342.     if (!(flags & HASWIDTH))
  343.     *flagp &= ~HASWIDTH;
  344.     *flagp |= flags & SPSTART;
  345.     while (*regparse == '|') {
  346.     regparse++;
  347.     br = regbranch(&flags);
  348.     if (br == NULL)
  349.         return (NULL);
  350.     regtail(ret, br);    /* BRANCH -> BRANCH. */
  351.     if (!(flags & HASWIDTH))
  352.         *flagp &= ~HASWIDTH;
  353.     *flagp |= flags & SPSTART;
  354.     }
  355.  
  356.     /* Make a closing node, and hook it on the end. */
  357.     ender = regnode((paren) ? CLOSE + parno : END);
  358.     regtail(ret, ender);
  359.  
  360.     /* Hook the tails of the branches to the closing node. */
  361.     for (br = ret; br != NULL; br = regnext(br))
  362.     regoptail(br, ender);
  363.  
  364.     /* Check for proper termination. */
  365.     if (paren && *regparse++ != ')') {
  366.     FAIL("unmatched ()");
  367.     } else if (!paren && *regparse != '\0') {
  368.     if (*regparse == ')') {
  369.         FAIL("unmatched ()");
  370.     } else
  371.         FAIL("junk on end");/* "Can't happen". */
  372.     /* NOTREACHED */
  373.     }
  374.     return (ret);
  375. }
  376.  
  377. /*
  378.  * - regbranch - one alternative of an | operator
  379.  *
  380.  * Implements the concatenation operator.
  381.  */
  382. static char    *
  383. regbranch(flagp)
  384.     int           *flagp;
  385. {
  386.     register char  *ret;
  387.     register char  *chain;
  388.     register char  *latest;
  389.     int            flags;
  390.  
  391.     *flagp = WORST;        /* Tentatively. */
  392.  
  393.     ret = regnode(BRANCH);
  394.     chain = NULL;
  395.     while (*regparse != '\0' && *regparse != '|' && *regparse != ')') {
  396.     latest = regpiece(&flags);
  397.     if (latest == NULL)
  398.         return (NULL);
  399.     *flagp |= flags & HASWIDTH;
  400.     if (chain == NULL)    /* First piece. */
  401.         *flagp |= flags & SPSTART;
  402.     else
  403.         regtail(chain, latest);
  404.     chain = latest;
  405.     }
  406.     if (chain == NULL)        /* Loop ran zero times. */
  407.     (void) regnode(NOTHING);
  408.  
  409.     return (ret);
  410. }
  411.  
  412. /*
  413.  * - regpiece - something followed by possible [*+?]
  414.  *
  415.  * Note that the branching code sequences used for ? and the general cases of *
  416.  * and + are somewhat optimized:  they use the same NOTHING node as both the
  417.  * endmarker for their branch list and the body of the last branch. It might
  418.  * seem that this node could be dispensed with entirely, but the endmarker
  419.  * role is not redundant.
  420.  */
  421. static char    *
  422. regpiece(flagp)
  423.     int           *flagp;
  424. {
  425.     register char  *ret;
  426.     register char   op;
  427.     register char  *next;
  428.     int            flags;
  429.  
  430.     ret = regatom(&flags);
  431.     if (ret == NULL)
  432.     return (NULL);
  433.  
  434.     op = *regparse;
  435.     if (!ISMULT(op)) {
  436.     *flagp = flags;
  437.     return (ret);
  438.     }
  439.     if (!(flags & HASWIDTH) && op != '?')
  440.     FAIL("*+ operand could be empty");
  441.     *flagp = (op != '+') ? (WORST | SPSTART) : (WORST | HASWIDTH);
  442.  
  443.     if (op == '*' && (flags & SIMPLE))
  444.     reginsert(STAR, ret);
  445.     else if (op == '*') {
  446.     /* Emit x* as (x&|), where & means "self". */
  447.     reginsert(BRANCH, ret); /* Either x */
  448.     regoptail(ret, regnode(BACK));    /* and loop */
  449.     regoptail(ret, ret);    /* back */
  450.     regtail(ret, regnode(BRANCH));    /* or */
  451.     regtail(ret, regnode(NOTHING)); /* null. */
  452.     } else if (op == '+' && (flags & SIMPLE))
  453.     reginsert(PLUS, ret);
  454.     else if (op == '+') {
  455.     /* Emit x+ as x(&|), where & means "self". */
  456.     next = regnode(BRANCH); /* Either */
  457.     regtail(ret, next);
  458.     regtail(regnode(BACK), ret);    /* loop back */
  459.     regtail(next, regnode(BRANCH)); /* or */
  460.     regtail(ret, regnode(NOTHING)); /* null. */
  461.     } else if (op == '?') {
  462.     /* Emit x? as (x|) */
  463.     reginsert(BRANCH, ret); /* Either x */
  464.     regtail(ret, regnode(BRANCH));    /* or */
  465.     next = regnode(NOTHING);/* null. */
  466.     regtail(ret, next);
  467.     regoptail(ret, next);
  468.     }
  469.     regparse++;
  470.     if (ISMULT(*regparse))
  471.     FAIL("nested *?+");
  472.  
  473.     return (ret);
  474. }
  475.  
  476. /*
  477.  * - regatom - the lowest level
  478.  *
  479.  * Optimization:  gobbles an entire sequence of ordinary characters so that it
  480.  * can turn them into a single node, which is smaller to store and faster to
  481.  * run.     Backslashed characters are exceptions, each becoming a separate
  482.  * node; the code is simpler that way and it's not worth fixing. 
  483.  */
  484. static char    *
  485. regatom(flagp)
  486.     int           *flagp;
  487. {
  488.     register char  *ret;
  489.     int            flags;
  490.  
  491.     *flagp = WORST;        /* Tentatively. */
  492.  
  493.     switch (*regparse++) {
  494.     case '^':
  495.     ret = regnode(BOL);
  496.     break;
  497.     case '$':
  498.     ret = regnode(EOL);
  499.     break;
  500.     case '.':
  501.     ret = regnode(ANY);
  502.     *flagp |= HASWIDTH | SIMPLE;
  503.     break;
  504.     case '[':{
  505.         register int    class;
  506.         register int    classend;
  507.  
  508.         if (*regparse == '^') {     /* Complement of range. */
  509.         ret = regnode(ANYBUT);
  510.         regparse++;
  511.         } else
  512.         ret = regnode(ANYOF);
  513.         if (*regparse == ']' || *regparse == '-')
  514.         regc(*regparse++);
  515.         while (*regparse != '\0' && *regparse != ']') {
  516.         if (*regparse == '-') {
  517.             regparse++;
  518.             if (*regparse == ']' || *regparse == '\0')
  519.             regc('-');
  520.             else {
  521.             class = UCHARAT(regparse - 2) + 1;
  522.             classend = UCHARAT(regparse);
  523.             if (class > classend + 1)
  524.                 FAIL("invalid [] range");
  525.             for (; class <= classend; class++)
  526.                 regc(class);
  527.             regparse++;
  528.             }
  529.         } else
  530.             regc(*regparse++);
  531.         }
  532.         regc('\0');
  533.         if (*regparse != ']')
  534.         FAIL("unmatched []");
  535.         regparse++;
  536.         *flagp |= HASWIDTH | SIMPLE;
  537.     }
  538.     break;
  539.     case '(':
  540.     ret = reg(1, &flags);
  541.     if (ret == NULL)
  542.         return (NULL);
  543.     *flagp |= flags & (HASWIDTH | SPSTART);
  544.     break;
  545.     case '\0':
  546.     case '|':
  547.     case ')':
  548.     FAIL("internal urp");   /* Supposed to be caught earlier. */
  549.     break;
  550.     case '?':
  551.     case '+':
  552.     case '*':
  553.     FAIL("?+* follows nothing");
  554.     break;
  555.     case '\\':
  556.     if (*regparse == '\0')
  557.         FAIL("trailing \\");
  558.     ret = regnode(EXACTLY);
  559.     regc(*regparse++);
  560.     regc('\0');
  561.     *flagp |= HASWIDTH | SIMPLE;
  562.     break;
  563.     default:{
  564.         register int    len;
  565.         register char   ender;
  566.  
  567.         regparse--;
  568.         len = strcspn(regparse, META);
  569.         if (len <= 0)
  570.         FAIL("internal disaster");
  571.         ender = *(regparse + len);
  572.         if (len > 1 && ISMULT(ender))
  573.         len--;        /* Back off clear of ?+* operand. */
  574.         *flagp |= HASWIDTH;
  575.         if (len == 1)
  576.         *flagp |= SIMPLE;
  577.         ret = regnode(EXACTLY);
  578.         while (len > 0) {
  579.         regc(*regparse++);
  580.         len--;
  581.         }
  582.         regc('\0');
  583.     }
  584.     break;
  585.     }
  586.  
  587.     return (ret);
  588. }
  589.  
  590. /*
  591.  * - regnode - emit a node
  592.  */
  593. static char    *        /* Location. */
  594. regnode(op)
  595.     char        op;
  596. {
  597.     register char  *ret;
  598.     register char  *ptr;
  599.  
  600.     ret = regcode;
  601.     if (ret == ®dummy) {
  602.     regsize += 3;
  603.     return (ret);
  604.     }
  605.     ptr = ret;
  606.     *ptr++ = op;
  607.     *ptr++ = '\0';              /* Null "next" pointer. */
  608.     *ptr++ = '\0';
  609.     regcode = ptr;
  610.  
  611.     return (ret);
  612. }
  613.  
  614. /*
  615.  * - regc - emit (if appropriate) a byte of code
  616.  */
  617. static void
  618. regc(b)
  619.     char        b;
  620. {
  621.     if (regcode != ®dummy)
  622.     *regcode++ = b;
  623.     else
  624.     regsize++;
  625. }
  626.  
  627. /*
  628.  * - reginsert - insert an operator in front of already-emitted operand
  629.  *
  630.  * Means relocating the operand.
  631.  */
  632. static void
  633. reginsert(op, opnd)
  634.     char        op;
  635.     char       *opnd;
  636. {
  637.     register char  *src;
  638.     register char  *dst;
  639.     register char  *place;
  640.  
  641.     if (regcode == ®dummy) {
  642.     regsize += 3;
  643.     return;
  644.     }
  645.     src = regcode;
  646.     regcode += 3;
  647.     dst = regcode;
  648.     while (src > opnd)
  649.     *--dst = *--src;
  650.  
  651.     place = opnd;        /* Op node, where operand used to be. */
  652.     *place++ = op;
  653.     *place++ = '\0';
  654.     *place++ = '\0';
  655. }
  656.  
  657. /*
  658.  * - regtail - set the next-pointer at the end of a node chain
  659.  */
  660. static void
  661. regtail(p, val)
  662.     char       *p;
  663.     char       *val;
  664. {
  665.     register char  *scan;
  666.     register char  *temp;
  667.     register int    offset;
  668.  
  669.     if (p == ®dummy)
  670.     return;
  671.  
  672.     /* Find last node. */
  673.     scan = p;
  674.     for (;;) {
  675.     temp = regnext(scan);
  676.     if (temp == NULL)
  677.         break;
  678.     scan = temp;
  679.     }
  680.  
  681.     if (OP(scan) == BACK)
  682.     offset = scan - val;
  683.     else
  684.     offset = val - scan;
  685.     *(scan + 1) = (offset >> 8) & 0377;
  686.     *(scan + 2) = offset & 0377;
  687. }
  688.  
  689. /*
  690.  * - regoptail - regtail on operand of first argument; nop if operandless
  691.  */
  692. static void
  693. regoptail(p, val)
  694.     char       *p;
  695.     char       *val;
  696. {
  697.     /* "Operandless" and "op != BRANCH" are synonymous in practice. */
  698.     if (p == NULL || p == ®dummy || OP(p) != BRANCH)
  699.     return;
  700.     regtail(OPERAND(p), val);
  701. }
  702.  
  703. /*
  704.  * regexec and friends
  705.  */
  706.  
  707. /*
  708.  * Global work variables for regexec().
  709.  */
  710. static char    *reginput;    /* String-input pointer. */
  711. static char    *regbol;        /* Beginning of input, for ^ check. */
  712. static char   **regstartp;    /* Pointer to startp array. */
  713. static char   **regendp;    /* Ditto for endp. */
  714.  
  715. /*
  716.  * Forwards.
  717.  */
  718. #ifdef __STDC__
  719. STATIC int    regtry(regexp *, char *);
  720. STATIC int    regmatch(char *);
  721. STATIC int    regrepeat(char *);
  722. #ifdef DEBUG
  723. int        regnarrate = 0;
  724. void        regdump(regexp *);
  725. STATIC char    *regprop(char *);
  726. #endif /* DEBUG */
  727. #else
  728. STATIC int    regtry();
  729. STATIC int    regmatch();
  730. STATIC int    regrepeat();
  731. #ifdef DEBUG
  732. int        regnarrate = 0;
  733. void        regdump();
  734. STATIC char    *regprop();
  735. #endif /* DEBUG */
  736. #endif /* __STDC__ */
  737.  
  738.  
  739. /*
  740.  * - regexec - match a regexp against a string
  741.  */
  742. int
  743. regexec(prog, string)
  744.     register regexp *prog;
  745.     register char  *string;
  746. {
  747.     register char  *s;
  748.  
  749.     /* Be paranoid... */
  750.     if (prog == NULL || string == NULL) {
  751.     regerror("NULL parameter");
  752.     return (0);
  753.     }
  754.     /* Check validity of program. */
  755.     if (UCHARAT(prog->program) != MAGIC) {
  756.     regerror("corrupted program");
  757.     return (0);
  758.     }
  759.     /* If there is a "must appear" string, look for it. */
  760.     if (prog->regmust != NULL) {
  761.     s = string;
  762.     while ((s = strchr(s, prog->regmust[0])) != NULL) {
  763.         if (strncmp(s, prog->regmust, prog->regmlen) == 0)
  764.         break;        /* Found it. */
  765.         s++;
  766.     }
  767.     if (s == NULL)        /* Not present. */
  768.         return (0);
  769.     }
  770.     /* Mark beginning of line for ^ . */
  771.     regbol = string;
  772.  
  773.     /* Simplest case:  anchored match need be tried only once. */
  774.     if (prog->reganch)
  775.     return (regtry(prog, string));
  776.  
  777.     /* Messy cases:  unanchored match. */
  778.     s = string;
  779.     if (prog->regstart != '\0')
  780.     /* We know what char it must start with. */
  781.     while ((s = strchr(s, prog->regstart)) != NULL) {
  782.         if (regtry(prog, s))
  783.         return (1);
  784.         s++;
  785.     }
  786.     else
  787.     /* We don't -- general case. */
  788.     do {
  789.         if (regtry(prog, s))
  790.         return (1);
  791.     } while (*s++ != '\0');
  792.  
  793.     /* Failure. */
  794.     return (0);
  795. }
  796.  
  797. /*
  798.  * - regtry - try match at specific point
  799.  */
  800. static int            /* 0 failure, 1 success */
  801. regtry(prog, string)
  802.     regexp       *prog;
  803.     char       *string;
  804. {
  805.     register int    i;
  806.     register char **sp;
  807.     register char **ep;
  808.  
  809.     reginput = string;
  810.     regstartp = prog->startp;
  811.     regendp = prog->endp;
  812.  
  813.     sp = prog->startp;
  814.     ep = prog->endp;
  815.     for (i = NSUBEXP; i > 0; i--) {
  816.     *sp++ = NULL;
  817.     *ep++ = NULL;
  818.     }
  819.     if (regmatch(prog->program + 1)) {
  820.     prog->startp[0] = string;
  821.     prog->endp[0] = reginput;
  822.     return (1);
  823.     } else
  824.     return (0);
  825. }
  826.  
  827. /*
  828.  * - regmatch - main matching routine
  829.  *
  830.  * Conceptually the strategy is simple:     check to see whether the current node
  831.  * matches, call self recursively to see whether the rest matches, and then
  832.  * act accordingly.  In practice we make some effort to avoid recursion, in
  833.  * particular by going through "ordinary" nodes (that don't need to know
  834.  * whether the rest of the match failed) by a loop instead of by recursion.
  835.  */
  836. static int            /* 0 failure, 1 success */
  837. regmatch(prog)
  838.     char       *prog;
  839. {
  840.     register char  *scan;    /* Current node. */
  841.     char       *next;    /* Next node. */
  842.  
  843.     scan = prog;
  844. #ifdef DEBUG
  845.     if (scan != NULL && regnarrate)
  846.     fprintf(stderr, "%s(\n", regprop(scan));
  847. #endif
  848.     while (scan != NULL) {
  849. #ifdef DEBUG
  850.     if (regnarrate)
  851.         fprintf(stderr, "%s...\n", regprop(scan));
  852. #endif
  853.     next = regnext(scan);
  854.  
  855.     switch (OP(scan)) {
  856.     case BOL:
  857.         if (reginput != regbol)
  858.         return (0);
  859.         break;
  860.     case EOL:
  861.         if (*reginput != '\0')
  862.         return (0);
  863.         break;
  864.     case ANY:
  865.         if (*reginput == '\0')
  866.         return (0);
  867.         reginput++;
  868.         break;
  869.     case EXACTLY:{
  870.         register int    len;
  871.         register char  *opnd;
  872.  
  873.         opnd = OPERAND(scan);
  874.         /* Inline the first character, for speed. */
  875.         if (*opnd != *reginput)
  876.             return (0);
  877.         len = strlen(opnd);
  878.         if (len > 1 && strncmp(opnd, reginput, len) != 0)
  879.             return (0);
  880.         reginput += len;
  881.         }
  882.         break;
  883.     case ANYOF:
  884.         if (*reginput == '\0' || strchr(OPERAND(scan), *reginput) == NULL)
  885.         return (0);
  886.         reginput++;
  887.         break;
  888.     case ANYBUT:
  889.         if (*reginput == '\0' || strchr(OPERAND(scan), *reginput) != NULL)
  890.         return (0);
  891.         reginput++;
  892.         break;
  893.     case NOTHING:
  894.         break;
  895.     case BACK:
  896.         break;
  897.     case OPEN + 1:
  898.     case OPEN + 2:
  899.     case OPEN + 3:
  900.     case OPEN + 4:
  901.     case OPEN + 5:
  902.     case OPEN + 6:
  903.     case OPEN + 7:
  904.     case OPEN + 8:
  905.     case OPEN + 9:{
  906.         register int    no;
  907.         register char  *save;
  908.  
  909.         no = OP(scan) - OPEN;
  910.         save = reginput;
  911.  
  912.         if (regmatch(next)) {
  913.             /*
  914.              * Don't set startp if some later invocation of the same
  915.              * parentheses already has.
  916.              */
  917.             if (regstartp[no] == NULL)
  918.             regstartp[no] = save;
  919.             return (1);
  920.         } else
  921.             return (0);
  922.         }
  923.         break;
  924.     case CLOSE + 1:
  925.     case CLOSE + 2:
  926.     case CLOSE + 3:
  927.     case CLOSE + 4:
  928.     case CLOSE + 5:
  929.     case CLOSE + 6:
  930.     case CLOSE + 7:
  931.     case CLOSE + 8:
  932.     case CLOSE + 9:{
  933.         register int    no;
  934.         register char  *save;
  935.  
  936.         no = OP(scan) - CLOSE;
  937.         save = reginput;
  938.  
  939.         if (regmatch(next)) {
  940.             /*
  941.              * Don't set endp if some later invocation of the same
  942.              * parentheses already has.
  943.              */
  944.             if (regendp[no] == NULL)
  945.             regendp[no] = save;
  946.             return (1);
  947.         } else
  948.             return (0);
  949.         }
  950.         break;
  951.     case BRANCH:{
  952.         register char  *save;
  953.  
  954.         if (OP(next) != BRANCH) /* No choice. */
  955.             next = OPERAND(scan);    /* Avoid recursion. */
  956.         else {
  957.             do {
  958.             save = reginput;
  959.             if (regmatch(OPERAND(scan)))
  960.                 return (1);
  961.             reginput = save;
  962.             scan = regnext(scan);
  963.             } while (scan != NULL && OP(scan) == BRANCH);
  964.             return (0);
  965.             /* NOTREACHED */
  966.         }
  967.         }
  968.         break;
  969.     case STAR:
  970.     case PLUS:{
  971.         register char    nextch;
  972.         register int    no;
  973.         register char  *save;
  974.         register int    min;
  975.  
  976.         /*
  977.          * Lookahead to avoid useless match attempts when we know
  978.          * what character comes next.
  979.          */
  980.         nextch = '\0';
  981.         if (OP(next) == EXACTLY)
  982.             nextch = *OPERAND(next);
  983.         min = (OP(scan) == STAR) ? 0 : 1;
  984.         save = reginput;
  985.         no = regrepeat(OPERAND(scan));
  986.         while (no >= min) {
  987.             /* If it could work, try it. */
  988.             if (nextch == '\0' || *reginput == nextch)
  989.             if (regmatch(next))
  990.                 return (1);
  991.             /* Couldn't or didn't -- back up. */
  992.             no--;
  993.             reginput = save + no;
  994.         }
  995.         return (0);
  996.         }
  997.         break;
  998.     case END:
  999.         return (1);        /* Success! */
  1000.         break;
  1001.     default:
  1002.         regerror("memory corruption");
  1003.         return (0);
  1004.         break;
  1005.     }
  1006.  
  1007.     scan = next;
  1008.     }
  1009.  
  1010.     /*
  1011.      * We get here only if there's trouble -- normally "case END" is the
  1012.      * terminating point.
  1013.      */
  1014.     regerror("corrupted pointers");
  1015.     return (0);
  1016. }
  1017.  
  1018. /*
  1019.  * - regrepeat - repeatedly match something simple, report how many
  1020.  */
  1021. static int
  1022. regrepeat(p)
  1023.     char       *p;
  1024. {
  1025.     register int    count = 0;
  1026.     register char  *scan;
  1027.     register char  *opnd;
  1028.  
  1029.     scan = reginput;
  1030.     opnd = OPERAND(p);
  1031.     switch (OP(p)) {
  1032.     case ANY:
  1033.     count = strlen(scan);
  1034.     scan += count;
  1035.     break;
  1036.     case EXACTLY:
  1037.     while (*opnd == *scan) {
  1038.         count++;
  1039.         scan++;
  1040.     }
  1041.     break;
  1042.     case ANYOF:
  1043.     while (*scan != '\0' && strchr(opnd, *scan) != NULL) {
  1044.         count++;
  1045.         scan++;
  1046.     }
  1047.     break;
  1048.     case ANYBUT:
  1049.     while (*scan != '\0' && strchr(opnd, *scan) == NULL) {
  1050.         count++;
  1051.         scan++;
  1052.     }
  1053.     break;
  1054.     default:            /* Oh dear.  Called inappropriately. */
  1055.     regerror("internal foulup");
  1056.     count = 0;        /* Best compromise. */
  1057.     break;
  1058.     }
  1059.     reginput = scan;
  1060.  
  1061.     return (count);
  1062. }
  1063.  
  1064. /*
  1065.  * - regnext - dig the "next" pointer out of a node 
  1066.  */
  1067. static char    *
  1068. regnext(p)
  1069.     register char  *p;
  1070. {
  1071.     register int    offset;
  1072.  
  1073.     if (p == ®dummy)
  1074.     return (NULL);
  1075.  
  1076.     offset = NEXT(p);
  1077.     if (offset == 0)
  1078.     return (NULL);
  1079.  
  1080.     if (OP(p) == BACK)
  1081.     return (p - offset);
  1082.     else
  1083.     return (p + offset);
  1084. }
  1085.  
  1086. #ifdef DEBUG
  1087.  
  1088. STATIC char    *regprop();
  1089.  
  1090. /*
  1091.  * - regdump - dump a regexp onto stdout in vaguely comprehensible form
  1092.  */
  1093. void
  1094. regdump(r)
  1095.     regexp       *r;
  1096. {
  1097.     register char  *s;
  1098.     register char   op = EXACTLY;    /* Arbitrary non-END op. */
  1099.     register char  *next;
  1100.  
  1101.  
  1102.     s = r->program + 1;
  1103.     while (op != END) {        /* While that wasn't END last time... */
  1104.     op = OP(s);
  1105.     printf("%2d%s", s - r->program, regprop(s));    /* Where, what. */
  1106.     next = regnext(s);
  1107.     if (next == NULL)    /* Next ptr. */
  1108.         printf("(0)");
  1109.     else
  1110.         printf("(%d)", (s - r->program) + (next - s));
  1111.     s += 3;
  1112.     if (op == ANYOF || op == ANYBUT || op == EXACTLY) {
  1113.         /* Literal string, where present. */
  1114.         while (*s != '\0') {
  1115.         putchar(*s);
  1116.         s++;
  1117.         }
  1118.         s++;
  1119.     }
  1120.     putchar('\n');
  1121.     }
  1122.  
  1123.     /* Header fields of interest. */
  1124.     if (r->regstart != '\0')
  1125.     printf("start `%c' ", r->regstart);
  1126.     if (r->reganch)
  1127.     printf("anchored ");
  1128.     if (r->regmust != NULL)
  1129.     printf("must have \"%s\"", r->regmust);
  1130.     printf("\n");
  1131. }
  1132.  
  1133. /*
  1134.  * - regprop - printable representation of opcode
  1135.  */
  1136. static char    *
  1137. regprop(op)
  1138.     char       *op;
  1139. {
  1140.     register char  *p;
  1141.     static char        buf[50];
  1142.  
  1143.     (void) strcpy(buf, ":");
  1144.  
  1145.     switch (OP(op)) {
  1146.     case BOL:
  1147.     p = "BOL";
  1148.     break;
  1149.     case EOL:
  1150.     p = "EOL";
  1151.     break;
  1152.     case ANY:
  1153.     p = "ANY";
  1154.     break;
  1155.     case ANYOF:
  1156.     p = "ANYOF";
  1157.     break;
  1158.     case ANYBUT:
  1159.     p = "ANYBUT";
  1160.     break;
  1161.     case BRANCH:
  1162.     p = "BRANCH";
  1163.     break;
  1164.     case EXACTLY:
  1165.     p = "EXACTLY";
  1166.     break;
  1167.     case NOTHING:
  1168.     p = "NOTHING";
  1169.     break;
  1170.     case BACK:
  1171.     p = "BACK";
  1172.     break;
  1173.     case END:
  1174.     p = "END";
  1175.     break;
  1176.     case OPEN + 1:
  1177.     case OPEN + 2:
  1178.     case OPEN + 3:
  1179.     case OPEN + 4:
  1180.     case OPEN + 5:
  1181.     case OPEN + 6:
  1182.     case OPEN + 7:
  1183.     case OPEN + 8:
  1184.     case OPEN + 9:
  1185.     sprintf(buf + strlen(buf), "OPEN%d", OP(op) - OPEN);
  1186.     p = NULL;
  1187.     break;
  1188.     case CLOSE + 1:
  1189.     case CLOSE + 2:
  1190.     case CLOSE + 3:
  1191.     case CLOSE + 4:
  1192.     case CLOSE + 5:
  1193.     case CLOSE + 6:
  1194.     case CLOSE + 7:
  1195.     case CLOSE + 8:
  1196.     case CLOSE + 9:
  1197.     sprintf(buf + strlen(buf), "CLOSE%d", OP(op) - CLOSE);
  1198.     p = NULL;
  1199.     break;
  1200.     case STAR:
  1201.     p = "STAR";
  1202.     break;
  1203.     case PLUS:
  1204.     p = "PLUS";
  1205.     break;
  1206.     default:
  1207.     regerror("corrupted opcode");
  1208.     break;
  1209.     }
  1210.     if (p != NULL)
  1211.     (void) strcat(buf, p);
  1212.     return (buf);
  1213. }
  1214. #endif
  1215.  
  1216. /*
  1217.  * The following is provided for those people who do not have strcspn() in
  1218.  * their C libraries.  They should get off their butts and do something about
  1219.  * it; at least one public-domain implementation of those (highly useful)
  1220.  * string routines has been published on Usenet.
  1221.  */
  1222. #ifdef STRCSPN
  1223. /*
  1224.  * strcspn - find length of initial segment of s1 consisting entirely of
  1225.  * characters not from s2
  1226.  */
  1227.  
  1228. static int
  1229. strcspn(s1, s2)
  1230.     char       *s1;
  1231.     char       *s2;
  1232. {
  1233.     register char  *scan1;
  1234.     register char  *scan2;
  1235.     register int    count;
  1236.  
  1237.     count = 0;
  1238.     for (scan1 = s1; *scan1 != '\0'; scan1++) {
  1239.     for (scan2 = s2; *scan2 != '\0';)       /* ++ moved down. */
  1240.         if (*scan1 == *scan2++)
  1241.         return (count);
  1242.     count++;
  1243.     }
  1244.     return (count);
  1245. }
  1246. #endif
  1247.